//排序数组
class Solution {
    vector<int> temp;

public:
    vector<int> sortArray(vector<int>& nums) {
        temp.resize(nums.size());
        mergesort(nums, 0, nums.size() - 1);
        return nums;
    }
    void mergesort(vector<int>& nums, int l, int r) {
        if (l >= r)
            return;
        int m = l + (r - l) / 2;
        mergesort(nums, l, m);
        mergesort(nums, m + 1, r);
        int cur1 = l, cur2 = m + 1, i = 0;
        while (cur1 <= m && cur2 <= r)
            temp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
        while (cur1 <= m)
            temp[i++] = nums[cur1++];
        while (cur2 <= r)
            temp[i++] = nums[cur2++];
        for (int i = l; i <= r; i++)
            nums[i] = temp[i - l];
    }
};

//交易逆序对的总数
//升序解决策略
class Solution {
    vector<int> temp;
    int ret;

public:
    int reversePairs(vector<int>& record) {
        temp.resize(record.size());
        int n = record.size();
        dfs(record, 0, n - 1);
        return ret;
    }
    void dfs(vector<int>& nums, int l, int r) {
        if (l >= r)
            return;
        int m = l + (r - l) / 2;
        dfs(nums, l, m);
        dfs(nums, m + 1, r);
        int cur1 = l, cur2 = m + 1, i = 0;
        while (cur1 <= m && cur2 <= r) {
            if (nums[cur1] <= nums[cur2]) {
                temp[i++] = nums[cur1++];
            } else {
                ret += (m - cur1 + 1);
                temp[i++] = nums[cur2++];
            }
        }
        while (cur1 <= m)
            temp[i++] = nums[cur1++];
        while (cur2 <= r)
            temp[i++] = nums[cur2++];
        for (int i = l; i <= r; i++)
            nums[i] = temp[i - l];
    }
};
//降序解决策略
class Solution {
    vector<int> temp;
    int ret;

public:
    int reversePairs(vector<int>& record) {
        temp.resize(record.size());
        int n = record.size();
        dfs(record, 0, n - 1);
        return ret;
    }
    void dfs(vector<int>& nums, int l, int r) {
        if (l >= r)
            return;
        int m = l + (r - l) / 2;
        dfs(nums, l, m);
        dfs(nums, m + 1, r);
        int cur1 = l, cur2 = m + 1, i = 0;
        while (cur1 <= m && cur2 <= r) {
            if (nums[cur1] > nums[cur2]) {
                ret += (r - cur2 + 1);
                temp[i++] = nums[cur1++];
            } else {
                temp[i++] = nums[cur2++];
            }
        }
        while (cur1 <= m)
            temp[i++] = nums[cur1++];
        while (cur2 <= r)
            temp[i++] = nums[cur2++];
        for (int i = l; i <= r; i++)
            nums[i] = temp[i - l];
    }
};
